package com.liunian.algorithmstudy.backtracking.hard;

public class SolveSudoku37 {

	/**
	 编写一个程序，通过填充空格来解决数独问题。
	 数独的解法需 遵循如下规则：
	 数字 1-9 在每一行只能出现一次。
	 数字 1-9 在每一列只能出现一次。
	 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）
	 数独部分空格内已填入了数字，空白格用 '.' 表示。
	 */
	public void solveSudoku(char[][] board) {
		backTracking(board);
	}

	private boolean backTracking(char[][] board) {
		for (int i = 0; i < board.length; i++) {
			for (int j = 0; j < board[0].length; j++) {
				if (board[i][j] == '.') {
					for (char k = '1'; k <= '9'; k++) {
						if (isValid(board, i, j, k)) {
							board[i][j] = k;
							if (backTracking(board)) {
								return true;
							}
							board[i][j] = '.';
						}
					}
					return false;
				}
			}
		}
		return true;
	}

	private boolean isValid(char[][] board, int row, int col, char val) {
		for (int i = 0; i < 9; i++) {
			if (board[i][col] == val) {
				return false;
			}
		}
		for (int i = 0; i < 9; i++) {
			if (board[row][i] == val) {
				return false;
			}
		}
		int startRow = (row / 3) * 3;
		int startCol = (col / 3) * 3;
		for (int i = startRow; i < startRow + 3; i++) {
			for (int j = startCol; j < startCol + 3; j++) {
				if (board[i][j] == val) {
					return false;
				}
			}
		}
		return true;
	}

}
